package Hot100;

/**
 * @author zhangmin
 * @create 2021-12-20 11:03
 */
public class findMedianSortedArrays4 {
    /**
     * 4. 寻找两个正序数组的中位数
     * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。
     * 1、双指针，遍历两个数组，当i+j==(n1+n2)/2
     * */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1=nums1.length,n2=nums2.length;
        int index=(n1+n2)/2;
        int[] m=new int[n1+n2];
        int i=0,j=0;
        for (int k = 0; k < m.length; k++) {
            if (i>=n1){
                m[k]=nums2[j];
                j++;
            }else if (j>=n2){
                m[k]=nums1[i];i++;
            }else if (nums1[i]<=nums2[j]){
                m[k]=nums1[i];
                i++;
            }else {
                m[k]=nums2[j];
                j++;
            }
            if (k==index){
                if ((n1+n2)%2==1) return m[k];
                else return (m[k]+m[k-1])/2.0;
            }
        }
        return -1;
    }

}
